public class Main {
    public static void main(String[] args) {
        Solution1 s = new Solution1();
        System.out.println(s.findKthLargest(new int[]{3,2,1,5,6,4}, 2));
        System.out.println(s.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4));
    }
}


//quickselect循环
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l = 0, h = nums.length - 1;
        while (true) {
            int mid = partition(nums, l, h);
            if (mid < k - 1) {
                l = mid + 1;
            } else if (mid > k - 1) {
                h = mid - 1;
            } else {
                return nums[mid];
            }
        }
    }

    int partition(int[] nums, int l, int h) {
        int picked = (int)(Math.random() * (h - l + 1)) + l;
        swap(nums, picked, h);
        int pivot = nums[h];
        int i = l, j = l;
        while (j <= h) {
            if (nums[j] >= pivot) {
                swap(nums, i++, j);
            }
            j++;
        }
        return i - 1;
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


//quickselect递归
class Solution1 {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int l, int h, int k) {
        int mid = partition(nums, l, h);
        if (mid < k - 1) {
            return quickSelect(nums, mid + 1, h, k);
        } else if (mid > k - 1) {
            return quickSelect(nums, l, mid - 1, k);
        } else {
            return nums[mid];
        }
    }

    private int partition(int[] nums, int l, int h) {
        int picked = (int)(Math.random() * (h - l + 1)) + l;
        swap(nums, picked, h);
        int pivot = nums[h];
        int i = l, j = l;
        while (j <= h) {
            if (nums[j] >= pivot) {
                swap(nums, i++, j);
            }
            j++;
        }
        return i - 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}